package 牛客.二分查找_排序;

public class BM19寻找峰值 {
    public int findPeakElement (int[] nums) {
        //二分法
        //核心：nums[mid]比右边元素大，那么右边下坡，可能存在峰值，右指针向左缩
        //     nums[mid]比右边元素小，那么右边上坡，一定存在峰值，左指针向右缩
        int left=0;
        int right=nums.length-1;

        while (left<right) {
            int mid=((right-left)>>2)+left;

            if (nums[mid]>nums[mid+1]) {
                //mid右边为下坡
                right=mid;
            }else {
                //mid右边仍为上坡
                left=mid+1;
            }
        }
        return left;

    }

    public int findPeakElement2 (int[] nums) {
        //暴力，直接找最大值
        int index=0;
        for (int i = 1; i <nums.length; i++) {
            if (nums[i]>nums[i-1]) {
                index=i;
            }
        }
        return index;
    }
    public int findPeakElement1 (int[] nums) {
        // write code here
        //暴力 蠢蛋做法
        if (nums.length == 1) {
            return 0;
        }
        if (nums.length == 2) {
            return nums[0] > nums[1] ?0 : 1;
        }
        for (int i = 1; i < nums.length-1 ; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
        int max=0;
        for (int i = 0; i < nums.length ; i++) {
            max=nums[max]<nums[i]?i:max;
        }
        return max;
    }
}
